package day30;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2022/12/30 9:03
 */

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.TreeSet;

/**
 * 在考场里，一排有 N 个座位，分别编号为 0, 1, 2, ..., N-1 。
 *
 * 当学生进入考场后，他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。)
 *
 * 返回 ExamRoom(int N) 类，它有两个公开的函数：其中，函数 ExamRoom.seat() 会返回一个 int （整型数据），代表学生坐的位置；函数 ExamRoom.leave(int p) 代表坐在座位 p 上的学生现在离开了考场。每次调用 ExamRoom.leave(p) 时都保证有学生坐在座位 p 上。
 *
 *
 *
 * 示例：
 *
 * 输入：["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
 * 输出：[null,0,9,4,2,null,5]
 * 解释：
 * ExamRoom(10) -> null
 * seat() -> 0，没有人在考场里，那么学生坐在 0 号座位上。
 * seat() -> 9，学生最后坐在 9 号座位上。
 * seat() -> 4，学生最后坐在 4 号座位上。
 * seat() -> 2，学生最后坐在 2 号座位上。
 * leave(4) -> null
 * seat() -> 5，学生最后坐在 5 号座位上。
 *
 */
public class ExamRoom {
    TreeSet<Integer> set;
    PriorityQueue<int[]> pq;
    int len;
    public ExamRoom(int n) {
        set = new TreeSet<>();
        pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                int num1 = o1[1]-o1[0],num2 = o2[1]-o2[0];
                return num1 / 2 < num2 / 2 || (num1 / 2 == num2 / 2 && o1[0] > o2[0]) ? 1 : -1;
            }
        });
        len = n;
    }

    public int seat() {
        if(set.isEmpty()){
            set.add(0);
            return 0;
        }
        int left = set.first(),right = len-1-set.last();
        while (set.size()>=2){
            int[] peek = pq.peek();
            if(set.contains(peek[0])&&set.contains(peek[1])&&set.higher(peek[0])==peek[1]){
                int num = peek[1]-peek[0];
                if(num/2<right||num/2<=left){
                    break;
                }
                pq.poll();
                pq.add(new int[]{peek[0],peek[0]+num/2});
                pq.add(new int[]{peek[0]+num/2,peek[1]});
                set.add(peek[0]+num/2);
                return peek[0]+num/2;
            }
            pq.poll();
        }
        if(right>left){
            pq.add(new int[]{set.last(),len-1});
            set.add(len-1);
            return len-1;
        }else {
            pq.add(new int[]{0,set.first()});
            set.add(0);
            return 0;
        }
    }

    public void leave(int p) {
        if (p != set.first() && p != set.last()) {
            int prev = set.lower(p), next = set.higher(p);
            pq.offer(new int[]{prev, next});
        }
        set.remove(p);
    }
}
